package fun.coding.leetcode;

public class AddTwoNumbers {

	public static void main(String[] args) {
		AddTwoNumbers instance = new AddTwoNumbers();
		/*
		int[] a1 = {2, 4, 3};
		int[] b1 = {6, 9};
		*/
		int[] a1 = {5};
		int[] b1 = {5};
		
		ListNode la1 = LeetCodeHelpers.buildLinkedList(a1);
		ListNode lb1 = LeetCodeHelpers.buildLinkedList(b1);
		ListNode res1 = instance.addTwoNumbers(la1, lb1);
		LeetCodeHelpers.printList(res1);

	}

	public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
		if (l1 == null && l2 == null) return null;
		
		ListNode dummyHead = new ListNode(-1);
		ListNode cur = dummyHead;
		int carry = 0;
		
		while (l1 != null && l2 != null) {
			int sum = l1.val + l2.val + carry;
			carry = sum / 10;
			int digit = sum % 10;
			cur.next = new ListNode(digit);
			cur = cur.next;
			
			l1 = l1.next;
			l2 = l2.next;
		}
		
		while (l1 != null) {
			int sum = l1.val + carry;
			carry = sum / 10;
			int digit = sum % 10;
			cur.next = new ListNode(digit);
			cur = cur.next;
			l1 = l1.next;
		}
		
		while (l2 != null) {
			int sum = l2.val + carry;
			carry = sum / 10;
			int digit = sum % 10;
			cur.next = new ListNode(digit);
			cur = cur.next;
			l2 = l2.next;
		}
		
		if (carry > 0) {
			ListNode t = new ListNode(carry);
			cur.next = t;
		}
		
		return dummyHead.next;
	}
	
	// Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
	// Output: 7 -> 0 -> 8
	// 342 + 465 = 807

	public ListNode addTwoNumbersOld(ListNode l1, ListNode l2) {
		ListNode head = null;
		ListNode it = null;
		
		// Don't need a boolean for carry, just need to divide it
		boolean isCarry = false;
		while (l1 != null && l2 != null) {
			int digit = l1.val + l2.val + (isCarry ? 1 : 0);
			
			if (digit >= 10) {
				isCarry = true;
				digit = digit % 10;
			} else {
				isCarry = false;
			}
			
			ListNode t = new ListNode(digit);
			// this code looks complicated because head pointer is uncertain. Use a dummy node
			if (head == null) {
				head = t;
				it = t;
			} else {
				it.next = t;
				it = t;
			}
			
			l1 = l1.next;
			l2 = l2.next;
		}
		
		while (l1 != null) {
			int digit = l1.val + (isCarry ? 1 : 0);
			
			if (digit >= 10) {
				isCarry = true;
				digit = digit % 10;
			} else {
				isCarry = false;
			}
			
			ListNode t = new ListNode(digit);
			if (head == null) {
				head = t;
				it = t;
			} else {
				it.next = t;
				it = t;
			}
			l1 = l1.next;
		}
		
		while (l2 != null) {
			int digit = l2.val + (isCarry ? 1 : 0);
			
			if (digit >= 10) {
				isCarry = true;
				digit = digit % 10;
			} else {
				isCarry = false;
			}
			
			ListNode t = new ListNode(digit);
			if (head == null) {
				head = t;
				it = t;
			} else {
				it.next = t;
				it = t;
			}
			l2 = l2.next;
		}
		
		// Don't forget about this case, 5+5 = 10
		if (isCarry) {
			ListNode t = new ListNode(1);
			it.next = t;
		}
		return head;
	}
}
